package LearnAlgorithm.f_字符串;

/*
X星球的考古学家发现了一批古代留下来的密码。

这些密码是由A、B、C、D 四种植物的种子串成的序列。

仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。

由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入格式
共一行，包含一个由大写字母ABCD构成的字符串，表示现在看到的密码串。

输出格式
输出一个整数，表示至少脱落了多少个种子。

输入样例1
ABCBA

输出样例1
0

输入样例2
ABDCDCBABC		//CBABDCDCDBABC

输出样例2
3
 */
public class j回文串例题之密码脱落 {
	public static void main(String[] args) {
		String string = "ABDCDCBABC";
//		System.out.println(findCode(string));
		System.out.println(findCodePlus(string));
	}
	
	public static int findCodePlus(String string) {
		char[] charArray = string.toCharArray();
		int count = 0;
		int leftCurrent = 0;
		int rightCurrent = string.length() - 1;
		int leftCount = 0;
		int rightCount = 0;
		while (leftCurrent < rightCurrent) {
			if (charArray[leftCurrent] == charArray[rightCurrent]) {
				leftCurrent++;
				rightCurrent--;
				continue;
			}
			int leftCursor = leftCurrent;
			while (charArray[leftCursor] != charArray[rightCurrent]) {
				leftCursor++;
				leftCount++;
			}
			int rightCursor = rightCurrent;
			while (charArray[rightCursor] != charArray[leftCurrent]) {
				rightCursor--;
				rightCount++;
			}
			if (leftCount < rightCount) {
				leftCurrent += leftCount;
			} else if (leftCount > rightCount) {
				rightCurrent -= rightCount;
			} else {//二者相等
				/*
				substring(0,5);截取从索引0到索引4的字符串片段作为新的字符串
				substring(5);去掉前5个字符，剩下的作为新的字符串
				这个过程我已经非常清楚并且没有一点错误
				将来再次看这里的我，你不懂的话可以去画图
				
				substring(0,1),这个方法会很人性化，直接返回""空串，不会报错
				如果string最大索引是8
				substring(9)会很人性化， 直接返回""空串，不会报错
				 */
				String rightString = new StringBuilder(string.substring(leftCurrent, leftCursor)).reverse().toString();
				String rightAfterString = string.substring(0, rightCurrent + 1) + rightString + string.substring(rightCurrent + 1);
				String leftString = new StringBuilder(string.substring(rightCursor + 1, rightCurrent + 1)).reverse().toString();
				String leftAfterString = string.subSequence(0, leftCurrent) + leftString + string.substring(leftCurrent);
				int rightAfterStringOfHanming = hanmingDistance(rightAfterString, new StringBuilder(rightAfterString).reverse().toString());
				int leftAfterStringOfHanming = hanmingDistance(leftAfterString, new StringBuilder(leftAfterString).reverse().toString());
				if (rightAfterStringOfHanming <= leftAfterStringOfHanming) {
					rightCurrent -= rightCount;
				} else {
					leftCurrent += leftCount;
				}
			}
			count += Math.min(rightCount, leftCount);
			leftCount = 0;
			rightCount = 0;
		}
		return count;
	}
	
	/**
	 * O(N^2)
	 * @param string
	 * @return
	 */
	public static int findCode(String string) {
		char[] charArray = string.toCharArray();
		int count = 0;//定义返回的数值
		int leftCurrent = 0;//定义左指针；初始化为第一个索引0
		int rightCurrent = string.length() - 1;//定义右指针；初始化为最后一个索引string.length() - 1
		int leftCount = 0;//定义冲突时，左指针，右移的推进次数
		int rightCount = 0;//定义冲突时，右指针，左移的推进次数
		while (leftCurrent < rightCurrent) {//循环结束条件是leftCurrent = rightCurrent
			if (charArray[leftCurrent] == charArray[rightCurrent]) {//如果两指针的元素相等
				leftCurrent++;//什么都不做仅仅把两指针推进
				rightCurrent--;
				continue;
			}//下面是如果不相等
			int leftCursor = leftCurrent;//定义临时左指针
			while (charArray[leftCursor] != charArray[rightCurrent]) {//直到临时左指针指向的元素=右指针指向的元素
				leftCursor++;//临时左指针右移推进
				leftCount++;//记录推进次数
			}
			int rightCursor = rightCurrent;//定义临时右指针
			while (charArray[rightCursor] != charArray[leftCurrent]) {//直到临时右指针指向的元素=左指针指向的元素
				rightCursor--;//临时右指针左移推进
				rightCount++;//记录推进次数
			}
			if (leftCount <= rightCount) {//判断左右推进次数哪个小；
				leftCurrent += leftCount;//左指针的小；左指针向右移动“leftCount”个元素
			} else {
				rightCurrent -= rightCount;//同上
			}
			count += Math.min(leftCurrent, rightCurrent);//谁小，总次数就加上谁
			//因为题目要求的是至少，所以谁小，count加谁
			leftCount = 0;//重置左推进次数
			rightCount = 0;//重置右推进次数
		}
		return count;
	}
	
	/**
	 * O(N)
	 * 汉明距离
	 * 两相同字符串的对应索引如果元素不同，汉明距离增加
	 * @param aString
	 * @param bString
	 * @return
	 */
	public static int hanmingDistance(String aString, String bString) {
		char[] aCharArray = aString.toCharArray();
		char[] bCharArray = bString.toCharArray();
		int distance = 0;
		for (int i = 0; i < aString.length(); i++) {
			if (aCharArray[i] != bCharArray[i]) {
				distance++;
			}
		}
		return distance;
	}
}
